That's a wrap

Problem
Code

Today's problem I wasn't sure how to tackle at first, but the first meandering idea I had, worked; thankfully.

Basically, we have to split a graph into two subgraphs, so that the two subgraphs are connected to each other by exactly three connections.

I chose to represent my graph the same as two days ago, as a Vec<Vec<usize>>, where graph[n] are the nodes reachable from node n.

The method I picked is relatively simple in concept, I think. We pick any arbitrary node as part of subgraph 1, keeping track of all nodes directly adjacent to it; and then we grow subgraph 1 by the neighbour that adds the fewest new reachable nodes.

I call the subgraph I'm building the "blob" (because it's amorphous and it grows?), and the border, well, "border". We keep growing the blob until the border is size 3.

let g = parse(input).ok_or("no parse")?;
let mut blob = HashSet::from([0]);
let mut border: HashSet<usize> = HashSet::from_iter(g[0].iter().copied());

while border.len() > 3 {
    // Find the node that would introduce the least new border nodes.
	let item = *border
		.iter()
		.min_by_key(|&&n| g[n].iter().filter(|conn| !blob.contains(conn)).count())
		.ok_or("unreachable")?;

	// Move the node from border to blob.
	border.remove(&item);
	blob.insert(item);

    // Add connections outside the blob to the border.
	for &conn in g[item].iter() {
		if !blob.contains(&conn) {
			border.insert(conn);
		}
	}
}

I'm not sure this method is guaranteed to work; didn't exactly prove it, I was just messing around with ideas. But, either way, we end up with blob containing all nodes in subgraph 1, and border containing exactly 3 elements.

Since subgraph 2 is simply all nodes not in subgraph 1, we can find the final result with a quick (g.len() - blob.len()) * blob.len().

Pretty happy to have finished another year, doing each day as it came.

In a few days, I think I'll write a short summary of my thoughts; since this was all a ploy to get used to writing code in Neovim (even though I stopped bringing it up!), I should probably mention how that's going, too!